graph.h

Go to the documentation of this file.
00001 /* graph.h */
00002 /*
00003         This software library implements the maxflow algorithm
00004         described in
00005 
00006                 "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision."
00007                 Yuri Boykov and Vladimir Kolmogorov.
00008                 In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 
00009                 September 2004
00010 
00011         This algorithm was developed by Yuri Boykov and Vladimir Kolmogorov
00012         at Siemens Corporate Research. To make it available for public use,
00013         it was later reimplemented by Vladimir Kolmogorov based on open publications.
00014 
00015         If you use this software for research purposes, you should cite
00016         the aforementioned paper in any resulting publication.
00017 
00018         ----------------------------------------------------------------------
00019 
00020         REUSING TREES:
00021 
00022         Starting with version 3.0, there is a also an option of reusing search
00023         trees from one maxflow computation to the next, as described in
00024 
00025                 "Efficiently Solving Dynamic Markov Random Fields Using Graph Cuts."
00026                 Pushmeet Kohli and Philip H.S. Torr
00027                 International Conference on Computer Vision (ICCV), 2005
00028 
00029         If you use this option, you should cite
00030         the aforementioned paper in any resulting publication.
00031 */
00032         
00033 
00034 
00035 /*
00036         For description, license, example usage see README.TXT.
00037 */
00038 
00039 #ifndef __GRAPH_H__
00040 #define __GRAPH_H__
00041 
00042 #include <string.h>
00043 #include "block.h"
00044 
00045 #include <assert.h>
00046 
00047 #include "dynamic/grow_vector.h"
00049 
00050 
00051 
00055 //
00057 template <typename captype, typename tcaptype, typename flowtype> class Graph
00058 {
00059 public:
00060         typedef enum
00061         {
00062                 SOURCE  = 0,
00063                 SINK    = 1
00064         } termtype; 
00065         typedef int node_id;
00066 
00071 
00085         Graph(int node_num_max, int edge_num_max, void (*err_function)(char *) = NULL);
00086 
00088         ~Graph();
00089 
00093         node_id add_node(int num = 1);
00094 
00097         void add_edge(node_id i, node_id j, captype cap, captype rev_cap);
00098 
00104         void add_tweights(node_id i, tcaptype cap_source, tcaptype cap_sink);
00105 
00106 
00110         flowtype maxflow(bool reuse_trees = false, Block<node_id>* changed_list = NULL);
00111 
00117         termtype what_segment(node_id i, termtype default_segm = SOURCE);
00118 
00119 
00120 
00122         //       ADVANCED INTERFACE FUNCTIONS       //
00123         //      (provide access to the graph)       //
00125 
00126 private:
00127         struct node;
00128         struct arc;
00129 
00130 public:
00131 
00133         // 1. Reallocating graph. //
00135 
00145         void reset();
00146 
00152 
00158         typedef arc* arc_id;
00159         arc_id get_first_arc();
00160         arc_id get_next_arc(arc_id a);
00161 
00163         int get_node_num() { return node_num; }
00164         int get_arc_num() { return (int)(arc_last - arcs); }
00165         void get_arc_ends(arc_id a, node_id& i, node_id& j); 
00166 
00170 
00172         tcaptype get_trcap(node_id i); 
00174         captype get_rcap(arc* a);
00175 
00181         void set_trcap(node_id i, tcaptype trcap); 
00182         void set_rcap(arc* a, captype rcap);
00183 
00187 
00208         void mark_node(node_id i);
00209 
00245         void remove_from_changed_list(node_id i) 
00246         { 
00247                 assert(i>=0 && i<node_num && nodes[i].is_in_changed_list); 
00248                 nodes[i].is_in_changed_list = 0;
00249         }
00250 
00251 
00252 
00253 
00254 
00255 
00259         
00260 private:
00262 
00263         struct node
00264         {
00265                 //fixed for a fixed graph
00266                 arc                     *first;         
00267 
00268 
00269                 //changed during computation
00270                 tcaptype        tr_cap;         
00271 
00272                 arc                     *parent;        
00273                 node            *next;          
00274                 int                     DIST;           
00275 
00276                 //changed only if one of the fields above is changed
00277                 int                     TS;                     
00278                 int                     is_sink : 1;    
00279                 int                     is_in_changed_list : 1; 
00280                 //changed outside:
00281                 int                     is_marked : 1;  
00282                 int                     is_saved : 1;
00283         };
00284 
00285         struct arc
00286         {
00287                 node            *head;          
00288                 arc                     *next;          
00289                 arc                     *sister;        
00290 
00291                 //changed during computation 
00292                 captype         r_cap;          
00293                 int                     is_saved : 1;
00294         };
00295 
00296         struct nodeptr
00297         {
00298                 node            *ptr;
00299                 nodeptr         *next;
00300         };
00301         static const int NODEPTR_BLOCK_SIZE = 128;
00302 
00303         node                            *nodes, *node_last, *node_max; 
00304         arc                                     *arcs, *arc_last, *arc_max; 
00305 
00306         int                                     node_num;
00307 
00308         DBlock<nodeptr>         *nodeptr_block;
00309 
00310         void    (*error_function)(char *);      
00311 
00312 
00313 
00314         flowtype                        flow;           
00315 
00317         int                                     maxflow_iteration; 
00318         Block<node_id>          *changed_list;
00319 
00321 
00322         node                            *queue_first[2], *queue_last[2];        
00323         nodeptr                         *orphan_first, *orphan_last;            
00324         int                                     TIME;                                                           
00325 
00327 
00328         void reallocate_nodes(int num); 
00329         void reallocate_arcs();
00330 
00332         void set_active(node *i);
00333         node *next_active();
00334 
00336         void set_orphan_front(node* i); 
00337         void set_orphan_rear(node* i);  
00338 
00339         void add_to_changed_list(node* i);
00340 
00341         void maxflow_init();             
00342         void maxflow_reuse_trees_init(); 
00343         void augment(arc *middle_arc);
00344         void process_source_orphan(node *i);
00345         void process_sink_orphan(node *i);
00346 
00347         void test_consistency(node* current_node=NULL); 
00348 private:
00349         class graph_save{
00350         public:
00351                 bool started;
00352                 struct node_saved{
00353                         node saved;
00354                         node * dest;
00355                         node_saved (node *x):dest(x),saved(*x){};
00356                 };
00357                 struct arc_saved{
00358                         arc saved;
00359                         arc * dest;
00360                         arc_saved (arc *x):dest(x),saved(*x){};
00361                 };
00362 
00363                 dynamic::grow_vector<node_saved> nodes;
00364                 dynamic::grow_vector<arc_saved> arcs;
00365                 flowtype flow;
00366                 int maxflow_iteration;
00367                 node                            *queue_first[2], *queue_last[2];        
00368                 nodeptr                         *orphan_first, *orphan_last;            
00369                 int                                     TIME;                                                           
00370                 //todo: save changed_list
00371         };
00372 
00373 public:
00374         graph_save save;
00375         void start_save(){
00376                 for(int i=0;i<save.nodes.size();++i){
00377                         save.nodes[i].dest->is_saved = false;
00378                 };
00379                 for(int i=0;i<save.arcs.size();++i){
00380                         save.arcs[i].dest->is_saved = false;
00381                 };
00382                 save.nodes.clear();
00383                 save.arcs.clear();
00384                 save.flow = flow;
00385                 save.maxflow_iteration = maxflow_iteration;
00386                 for(int i=0;i<2;++i){
00387                         save.queue_first[i] = queue_first[i];
00388                         save.queue_last[i] = queue_last[i];
00389                 };
00390                 save.TIME = TIME;
00391                 save.started = true;
00392         };
00393         void stop_save(){
00394                 save.started = false;
00395         };
00396 
00397         void restore_arc(arc * dest, const arc & s){
00398                 dest->r_cap = s.r_cap;
00399         };
00400 
00401         void restore_node(node * dest, const node & s){
00402                 dest->next = s.next;
00403                 dest->parent = s.parent;
00404                 dest->tr_cap = s.tr_cap;
00405                 //
00406                 dest->DIST = s.DIST;
00407                 //dest->is_marked = s.is_marked;
00408                 dest->is_sink = s.is_sink;
00409                 dest->TS = s.TS;
00410         };
00411 
00412         void restore_saved(){
00413                 for(int i=0;i<save.nodes.size();++i){
00414                         restore_node(save.nodes[i].dest,save.nodes[i].saved);
00415                 };
00416                 for(int i=0;i<save.arcs.size();++i){
00417                         restore_arc(save.arcs[i].dest,save.arcs[i].saved);
00418                 };
00419                 flow = save.flow;
00420                 maxflow_iteration = save.maxflow_iteration;
00421                 for(int i=0;i<2;++i){
00422                         queue_first[i] = save.queue_first[i];
00423                         queue_last[i] = save.queue_last[i];
00424                 };
00425                 TIME = save.TIME;
00426         };
00427 
00428         void save_node(node * x){
00429                 save.nodes.push_back(graph_save::node_saved(x));
00430         };
00431 
00432         void save_arc(arc * x){
00433                 save.arcs.push_back(graph_save::arc_saved(x));
00434         };
00435 
00436         void save(node * x){
00437                 if(save.started && !x->is_saved){
00438                         save_node(x);
00439                         x->is_saved = true;
00440                 };
00441         };
00442 
00443         void save(node & x){
00444                 save(&x);
00445         };
00446 
00447         void save(arc * x){
00448                 if(save.started && !x->is_saved){
00449                         save_arc(x);
00450                         x->is_saved = true;
00451                 };
00452         };
00453 
00454         void save(arc & x){
00455                 save(&x);
00456         };
00457 };
00458 
00459 
00460 
00461 
00462 
00463 
00464 
00465 
00466 
00467 
00468 
00472 
00473 
00474 
00475 template <typename captype, typename tcaptype, typename flowtype> 
00476         inline typename Graph<captype,tcaptype,flowtype>::node_id Graph<captype,tcaptype,flowtype>::add_node(int num)
00477 {
00478         assert(num > 0);
00479 
00480         if (node_last + num > node_max) reallocate_nodes(num);
00481 
00482         if (num == 1)
00483         {
00484                 node_last -> first = NULL;
00485                 node_last -> tr_cap = 0;
00486                 node_last -> is_marked = 0;
00487                 node_last -> is_in_changed_list = 0;
00488 
00489                 node_last ++;
00490                 return node_num++;
00491         }
00492         else
00493         {
00494                 memset(node_last, 0, num*sizeof(node));
00495 
00496                 node_id i = node_num;
00497                 node_num += num;
00498                 node_last += num;
00499                 return i;
00500         }
00501 }
00502 
00503 template <typename captype, typename tcaptype, typename flowtype> 
00504         inline void Graph<captype,tcaptype,flowtype>::add_tweights(node_id i, tcaptype cap_source, tcaptype cap_sink)
00505 {
00506         assert(i >= 0 && i < node_num);
00507 
00508         tcaptype delta = nodes[i].tr_cap;
00509         if (delta > 0) cap_source += delta;
00510         else           cap_sink   -= delta;
00511         flow += (cap_source < cap_sink) ? cap_source : cap_sink;
00512         save(nodes[i]);
00513         nodes[i].tr_cap = cap_source - cap_sink;
00514 }
00515 
00516 template <typename captype, typename tcaptype, typename flowtype> 
00517         inline void Graph<captype,tcaptype,flowtype>::add_edge(node_id _i, node_id _j, captype cap, captype rev_cap)
00518 {
00519         assert(_i >= 0 && _i < node_num);
00520         assert(_j >= 0 && _j < node_num);
00521         assert(_i != _j);
00522         assert(cap >= 0);
00523         assert(rev_cap >= 0);
00524 
00525         if (arc_last == arc_max) reallocate_arcs();
00526 
00527         arc *a = arc_last ++;
00528         arc *a_rev = arc_last ++;
00529 
00530         node* i = nodes + _i;
00531         node* j = nodes + _j;
00532         
00533         a -> sister = a_rev;
00534         a_rev -> sister = a;
00535         a -> next = i -> first;
00536         i -> first = a;
00537         a_rev -> next = j -> first;
00538         j -> first = a_rev;
00539         a -> head = j;
00540         a_rev -> head = i;
00541         a -> r_cap = cap;
00542         a_rev -> r_cap = rev_cap;
00543 }
00544 
00545 template <typename captype, typename tcaptype, typename flowtype> 
00546         inline typename Graph<captype,tcaptype,flowtype>::arc* Graph<captype,tcaptype,flowtype>::get_first_arc()
00547 {
00548         return arcs;
00549 }
00550 
00551 template <typename captype, typename tcaptype, typename flowtype> 
00552         inline typename Graph<captype,tcaptype,flowtype>::arc* Graph<captype,tcaptype,flowtype>::get_next_arc(arc* a) 
00553 {
00554         return a + 1; 
00555 }
00556 
00557 template <typename captype, typename tcaptype, typename flowtype> 
00558         inline void Graph<captype,tcaptype,flowtype>::get_arc_ends(arc* a, node_id& i, node_id& j)
00559 {
00560         assert(a >= arcs && a < arc_last);
00561         i = (node_id) (a->sister->head - nodes);
00562         j = (node_id) (a->head - nodes);
00563 }
00564 
00565 template <typename captype, typename tcaptype, typename flowtype> 
00566         inline tcaptype Graph<captype,tcaptype,flowtype>::get_trcap(node_id i)
00567 {
00568         assert(i>=0 && i<node_num);
00569         return nodes[i].tr_cap;
00570 }
00571 
00572 template <typename captype, typename tcaptype, typename flowtype> 
00573         inline captype Graph<captype,tcaptype,flowtype>::get_rcap(arc* a)
00574 {
00575         assert(a >= arcs && a < arc_last);
00576         return a->r_cap;
00577 }
00578 
00579 template <typename captype, typename tcaptype, typename flowtype> 
00580         inline void Graph<captype,tcaptype,flowtype>::set_trcap(node_id i, tcaptype trcap)
00581 {
00582         assert(i>=0 && i<node_num);
00583         save(nodes[i]);
00584         nodes[i].tr_cap = trcap;
00585 }
00586 
00587 template <typename captype, typename tcaptype, typename flowtype> 
00588         inline void Graph<captype,tcaptype,flowtype>::set_rcap(arc* a, captype rcap)
00589 {
00590         assert(a >= arcs && a < arc_last);
00591         a->r_cap = rcap;
00592 }
00593 
00594 
00595 template <typename captype, typename tcaptype, typename flowtype> 
00596         inline typename Graph<captype,tcaptype,flowtype>::termtype Graph<captype,tcaptype,flowtype>::what_segment(node_id i, termtype default_segm)
00597 {
00598         if (nodes[i].parent)
00599         {
00600                 return (nodes[i].is_sink) ? SINK : SOURCE;
00601         }
00602         else
00603         {
00604                 return default_segm;
00605         }
00606 }
00607 
00608 template <typename captype, typename tcaptype, typename flowtype> 
00609         inline void Graph<captype,tcaptype,flowtype>::mark_node(node_id _i)
00610 {
00611         node* i = nodes + _i;
00612         if (!i->next)
00613         {
00614                 /* it's not in the list yet */
00615                 if (queue_last[1]) queue_last[1] -> next = i;
00616                 else               queue_first[1]        = i;
00617                 queue_last[1] = i;
00618                 i -> next = i;
00619         }
00620         i->is_marked = 1;
00621 }
00622 
00623 
00624 #endif

Generated on Sun Oct 26 18:22:20 2008 for maxflow-v3.0 by  doxygen 1.4.7